package Other.CountBits;

//338. 比特位计数
public class CB {
    public static void main(String[] args) {
        Solution s = new Solution();
        s.countBits(8);
    }        
}


class Solution {
    public int[] countBits(int num) {
        int[] ans = new int[num+1];
        ans[0]=0;
        int flag=1;
        for (int i = 1; i < ans.length; i++) {
            if(i==(flag<<1)){
                ans[i]=1;
                flag=i;
            }else{
                ans[i]=1+ans[i-flag];
            }
        }
        return ans;
    }
}